home *** CD-ROM | disk | FTP | other *** search
/ BBS in a Box 5 / BBS in a Box -Volume V (BBS in a Box) (April 1992).iso / Files / Prog / M / MPWGCC (Misc).cpt / Bison / Documents / Info / bison.info-4 < prev    next >
Encoding:
Text File  |  1989-05-30  |  19.1 KB  |  589 lines  |  [TEXT/MPS ]
  1. Info file bison.info, produced by Makeinfo, -*- Text -*- from input
  2. file bison.texinfo.
  3.  
  4. This file documents the Bison parser generator.
  5.  
  6. Copyright (C) 1988, 1989 Free Software Foundation, Inc.
  7.  
  8. Permission is granted to make and distribute verbatim copies of this
  9. manual provided the copyright notice and this permission notice are
  10. preserved on all copies.
  11.  
  12. Permission is granted to copy and distribute modified versions of
  13. this manual under the conditions for verbatim copying, provided also
  14. that the sections entitled ``GNU General Public License'' and
  15. ``Conditions for Using Bison'' are included exactly as in the
  16. original, and provided that the entire resulting derived work is
  17. distributed under the terms of a permission notice identical to this
  18. one.
  19.  
  20. Permission is granted to copy and distribute translations of this
  21. manual into another language, under the above conditions for modified
  22. versions, except that the sections entitled ``GNU General Public
  23. License'', ``Conditions for Using Bison'' and this permission notice
  24. may be included in translations approved by the Free Software
  25. Foundation instead of in the original English.
  26.  
  27.  
  28. 
  29. File: bison.info,  Node: Table of Symbols,  Next: Glossary,  Prev: Invocation,  Up: Top
  30.  
  31. Table of Bison Symbols
  32. **********************
  33.  
  34. `error'
  35.      A token name reserved for error recovery.  This token may be
  36.      used in grammar rules so as to allow the Bison parser to
  37.      recognize an error in the grammar without halting the process. 
  38.      In effect, a sentence containing an error may be recognized as
  39.      valid.  On a parse error, the token `error' becomes the current
  40.      look-ahead token.  Actions corresponding to `error' are then
  41.      executed, and the look-ahead token is reset to the token that
  42.      originally caused the violation.  *Note Error Recovery::.
  43.  
  44. `YYABORT'
  45.      Macro to pretend that an unrecoverable syntax error has
  46.      occurred, by making `yyparse' return 1 immediately.  The error
  47.      reporting function `yyerror' is not called.  *Note Parser
  48.      Function::.
  49.  
  50. `YYACCEPT'
  51.      Macro to pretend that a complete utterance of the language has
  52.      been read, by making `yyparse' return 0 immediately.  *Note
  53.      Parser Function::.
  54.  
  55. `YYERROR'
  56.      Macro to pretend that a syntax error has just been detected:
  57.      call `yyerror' and then perform normal error recovery if
  58.      possible (*note Error Recovery::.), or (if recovery is
  59.      impossible) make `yyparse' return 1.  *Note Error Recovery::.
  60.  
  61. `YYLTYPE'
  62.      Macro for the data type of `yylloc'; a structure with four
  63.      members.  *Note Token Positions::.
  64.  
  65. `YYSTYPE'
  66.      Macro for the data type of semantic values; `int' by default. 
  67.      *Note Value Type::.
  68.  
  69. `yychar'
  70.      External integer variable that contains the integer value of the
  71.      current look-ahead token.  (In a pure parser, it is a local
  72.      variable within `yyparse'.)  Error-recovery rule actions may
  73.      examine this variable.  *Note Action Features::.
  74.  
  75. `yyclearin'
  76.      Macro used in error-recovery rule actions.  It clears the
  77.      previous look-ahead token.  *Note Error Recovery::.
  78.  
  79. `yydebug'
  80.      External integer variable set to zero by default.  If `yydebug'
  81.      is given a nonzero value, the parser will output information on
  82.      input symbols and parser action.  *Note Debugging::.
  83.  
  84. `yyerrok'
  85.      Macro to cause parser to recover immediately to its normal mode
  86.      after a parse error.  *Note Error Recovery::.
  87.  
  88. `yyerror'
  89.      User-supplied function to be called by `yyparse' on error.  The
  90.      function receives one argument, a pointer to a character string
  91.      containing an error message.  *Note Error Reporting::.
  92.  
  93. `yylex'
  94.      User-supplied lexical analyzer function, called with no
  95.      arguments to get the next token.  *Note Lexical::.
  96.  
  97. `yylval'
  98.      External variable in which `yylex' should place the semantic
  99.      value associated with a token.  (In a pure parser, it is a local
  100.      variable within `yyparse', and its address is passed to
  101.      `yylex'.)  *Note Token Values::.
  102.  
  103. `yylloc'
  104.      External variable in which `yylex' should place the line and
  105.      column numbers associated with a token.  (In a pure parser, it
  106.      is a local variable within `yyparse', and its address is passed
  107.      to `yylex'.)  You can ignore this variable if you don't use the
  108.      `@' feature in the grammar actions.  *Note Token Positions::.
  109.  
  110. `yynerrs'
  111.      Global variable which Bison increments each time there is a
  112.      parse error.  (In a pure parser, it is a local variable within
  113.      `yyparse'.)  *Note Error Reporting::.
  114.  
  115. `yyparse'
  116.      The parser function produced by Bison; call this function to
  117.      start parsing.  *Note Parser Function::.
  118.  
  119. `%left'
  120.      Bison declaration to assign left associativity to token(s). 
  121.      *Note Precedence Decl::.
  122.  
  123. `%nonassoc'
  124.      Bison declaration to assign nonassociativity to token(s).  *Note
  125.      Precedence Decl::.
  126.  
  127. `%prec'
  128.      Bison declaration to assign a precedence to a specific rule. 
  129.      *Note Contextual Precedence::.
  130.  
  131. `%pure_parser'
  132.      Bison declaration to request a pure (reentrant) parser.  *Note
  133.      Pure Decl::.
  134.  
  135. `%right'
  136.      Bison declaration to assign right associativity to token(s). 
  137.      *Note Precedence Decl::.
  138.  
  139. `%start'
  140.      Bison declaration to specify the start symbol.  *Note Start
  141.      Decl::.
  142.  
  143. `%token'
  144.      Bison declaration to declare token(s) without specifying
  145.      precedence.  *Note Token Decl::.
  146.  
  147. `%type'
  148.      Bison declaration to declare nonterminals.  *Note Type Decl::.
  149.  
  150. `%union'
  151.      Bison declaration to specify several possible data types for
  152.      semantic values.  *Note Union Decl::.
  153.  
  154. These are the punctuation and delimiters used in Bison input:
  155.  
  156. `%%'
  157.      Delimiter used to separate the grammar rule section from the
  158.      Bison declarations section or the additional C code section. 
  159.      *Note Grammar Layout::.
  160.  
  161. `%{ %}'
  162.      All code listed between `%{' and `%}' is copied directly to the
  163.      output file uninterpreted.  Such code forms the ``C
  164.      declarations'' section of the input file.  *Note Grammar
  165.      Outline::.
  166.  
  167. `/*...*/'
  168.      Comment delimiters, as in C.
  169.  
  170. `:'
  171.      Separates a rule's result from its components.  *Note Rules::.
  172.  
  173. `;'
  174.      Terminates a rule.  *Note Rules::.
  175.  
  176. `|'
  177.      Separates alternate rules for the same result nonterminal. 
  178.      *Note Rules::.
  179.  
  180.  
  181. 
  182. File: bison.info,  Node: Glossary,  Next: Index,  Prev: Table of Symbols,  Up: top
  183.  
  184. Glossary
  185. ********
  186.  
  187. Backus-Naur Form (BNF)
  188.      Formal method of specifying context-free grammars.  BNF was
  189.      first used in the ``ALGOL-60'' report, 1963.  *Note Language and
  190.      Grammar::.
  191.  
  192. Context-free grammars
  193.      Grammars specified as rules that can be applied regardless of
  194.      context.  Thus, if there is a rule which says that an integer
  195.      can be used as an expression, integers are allowed *anywhere* an
  196.      expression is permitted.  *Note Language and Grammar::.
  197.  
  198. Dynamic allocation
  199.      Allocation of memory that occurs during execution, rather than
  200.      at compile time or on entry to a function.
  201.  
  202. Empty string
  203.      Analogous to the empty set in set theory, the empty string is a
  204.      character string of length zero.
  205.  
  206. Finite-state stack machine
  207.      A ``machine'' that has discrete states in which it is said to
  208.      exist at each instant in time.  As input to the machine is
  209.      processed, the machine moves from state to state as specified by
  210.      the logic of the machine.  In the case of the parser, the input
  211.      is the language being parsed, and the states correspond to
  212.      various stages in the grammar rules.  *Note Algorithm::.
  213.  
  214. Grouping
  215.      A language construct that is (in general) grammatically
  216.      divisible; for example, `expression' or `declaration' in C. 
  217.      *Note Language and Grammar::.
  218.  
  219. Infix operator
  220.      An arithmetic operator that is placed between the operands on
  221.      which it performs some operation.
  222.  
  223. Input stream
  224.      A continuous flow of data between devices or programs.
  225.  
  226. Language construct
  227.      One of the typical usage schemas of the language.  For example,
  228.      one of the constructs of the C language is the `if' statement. 
  229.      *Note Language and Grammar::.
  230.  
  231. Left associativity
  232.      Operators having left associativity are analyzed from left to
  233.      right: `a+b+c' first computes `a+b' and then combines with `c'. 
  234.      *Note Precedence::.
  235.  
  236. Left recursion
  237.      A rule whose result symbol is also its first component symbol;
  238.      for example, `expseq1 : expseq1 ',' exp;'.  *Note Recursion::.
  239.  
  240. Left-to-right parsing
  241.      Parsing a sentence of a language by analyzing it token by token
  242.      from left to right.  *Note Algorithm::.
  243.  
  244. Lexical analyzer (scanner)
  245.      A function that reads an input stream and returns tokens one by
  246.      one.  *Note Lexical::.
  247.  
  248. Lexical tie-in
  249.      A flag, set by actions in the grammar rules, which alters the
  250.      way tokens are parsed.  *Note Lexical Tie-ins::.
  251.  
  252. Look-ahead token
  253.      A token already read but not yet shifted.  *Note Look-Ahead::.
  254.  
  255. Nonterminal symbol
  256.      A grammar symbol standing for a grammatical construct that can
  257.      be expressed through rules in terms of smaller constructs; in
  258.      other words, a construct that is not a token.  *Note Symbols::.
  259.  
  260. Parse error
  261.      An error encountered during parsing of an input stream due to
  262.      invalid syntax.  *Note Error Recovery::.
  263.  
  264. Parser
  265.      A function that recognizes valid sentences of a language by
  266.      analyzing the syntax structure of a set of tokens passed to it
  267.      from a lexical analyzer.
  268.  
  269. Postfix operator
  270.      An arithmetic operator that is placed after the operands upon
  271.      which it performs some operation.
  272.  
  273. Reduction
  274.      Replacing a string of nonterminals and/or terminals with a
  275.      single nonterminal, according to a grammar rule.  *Note
  276.      Algorithm::.
  277.  
  278. Reentrant
  279.      A reentrant subprogram is a subprogram which can be in invoked
  280.      any number of times in parallel, without interference between
  281.      the various invocations.  *Note Pure Decl::.
  282.  
  283. Reverse polish notation
  284.      A language in which all operators are postfix operators.
  285.  
  286. Right recursion
  287.      A rule whose result symbol is also its last component symbol;
  288.      for example, `expseq1: exp ',' expseq1;'.  *Note Recursion::.
  289.  
  290. Semantics
  291.      In computer languages the semantics are specified by the actions
  292.      taken for each instance of the language, i.e., the meaning of
  293.      each statement.  *Note Semantics::.
  294.  
  295. Shift
  296.      A parser is said to shift when it makes the choice of analyzing
  297.      further input from the stream rather than reducing immediately
  298.      some already-recognized rule.  *Note Algorithm::.
  299.  
  300. Single-character literal
  301.      A single character that is recognized and interpreted as is. 
  302.      *Note Grammar in Bison::.
  303.  
  304. Start symbol
  305.      The nonterminal symbol that stands for a complete valid
  306.      utterance in the language being parsed.  The start symbol is
  307.      usually listed as the first nonterminal symbol in a language
  308.      specification.  *Note Start Decl::.
  309.  
  310. Symbol table
  311.      A data structure where symbol names and associated data are
  312.      stored during parsing to allow for recognition and use of
  313.      existing information in repeated uses of a symbol.  *Note
  314.      Multi-function Calc::.
  315.  
  316. Token
  317.      A basic, grammatically indivisible unit of a language.  The
  318.      symbol that describes a token in the grammar is a terminal symbol.
  319.      The input of the Bison parser is a stream of tokens which comes
  320.      from the lexical analyzer.  *Note Symbols::.
  321.  
  322. Terminal symbol
  323.      A grammar symbol that has no rules in the grammar and therefore
  324.      is grammatically indivisible.  The piece of text it represents
  325.      is a token.  *Note Language and Grammar::.
  326.  
  327.  
  328. 
  329. File: bison.info,  Node: Index,  Prev: Glossary,  Up: top
  330.  
  331. Index
  332. *****
  333.  
  334. * Menu:
  335.  
  336. * $$: Actions.
  337. * $N: Actions.
  338. * %expect: Expect Decl.
  339. * %left: Using Precedence.
  340. * %nonassoc: Using Precedence.
  341. * %prec: Contextual Precedence.
  342. * %pure_parser: Pure Decl.
  343. * %right: Using Precedence.
  344. * %start: Start Decl.
  345. * %token: Token Decl.
  346. * %type: Type Decl.
  347. * %union: Union Decl.
  348. * @N: Action Features.
  349. * `calc': Infix Calc.
  350. * `else', dangling: Shift/Reduce.
  351. * `mfcalc': Multi-function Calc.
  352. * `rpcalc': RPN Calc.
  353. * BNF: Language and Grammar.
  354. * Backus-Naur form: Language and Grammar.
  355. * Bison declaration summary: Decl Summary.
  356. * Bison declarations: Declarations.
  357. * Bison declarations section (introduction): Bison Declarations.
  358. * Bison grammar: Grammar in Bison.
  359. * Bison invocation: Invocation.
  360. * Bison parser: Bison Parser.
  361. * Bison symbols, table of: Table of Symbols.
  362. * Bison utility: Bison Parser.
  363. * C code, section for additional: C Code.
  364. * C declarations section: C Declarations.
  365. * C-language interface: Interface.
  366. * YYABORT: Parser Function.
  367. * YYACCEPT: Parser Function.
  368. * YYDEBUG: Debugging.
  369. * action: Actions.
  370. * action data types: Action Types.
  371. * action features summary: Action Features.
  372. * actions in mid-rule: Mid-Rule Actions.
  373. * actions, semantic: Semantic Actions.
  374. * additional C code section: C Code.
  375. * algorithm of parser: Algorithm.
  376. * associativity: Why Precedence.
  377. * calculator, infix notation: Infix Calc.
  378. * calculator, multi-function: Multi-function Calc.
  379. * calculator, simple: RPN Calc.
  380. * character token: Symbols.
  381. * compiling the parser: Rpcalc Compile.
  382. * conflicts: Shift/Reduce.
  383. * conflicts, preventing warnings of: Expect Decl.
  384. * context-dependent precedence: Contextual Precedence.
  385. * context-free grammar: Language and Grammar.
  386. * controlling function: Rpcalc Main.
  387. * dangling `else': Shift/Reduce.
  388. * data types in actions: Action Types.
  389. * data types of semantic values: Value Type.
  390. * debugging: Debugging.
  391. * declaration summary: Decl Summary.
  392. * declarations section, Bison (introduction): Bison Declarations.
  393. * declarations, Bison: Declarations.
  394. * declarations, C: C Declarations.
  395. * declaring operator precedence: Precedence Decl.
  396. * declaring the start-symbol: Start Decl.
  397. * declaring token type names: Token Decl.
  398. * declaring value types: Union Decl.
  399. * declaring value types, nonterminals: Type Decl.
  400. * error: Error Recovery.
  401. * error recovery: Error Recovery.
  402. * error recovery, simple: Simple Error Recovery.
  403. * error reporting function: Error Reporting.
  404. * error reporting routine: Rpcalc Error.
  405. * examples, simple: Examples.
  406. * exercises: Exercises.
  407. * finite-state machine: Parser States.
  408. * formal grammar: Grammar in Bison.
  409. * glossary: Glossary.
  410. * grammar file: Grammar Layout.
  411. * grammar rule syntax: Rules.
  412. * grammar rules section: Grammar Rules.
  413. * grammar, context-free: Language and Grammar.
  414. * grouping, syntactic: Language and Grammar.
  415. * infix notation calculator: Infix Calc.
  416. * interface: Interface.
  417. * introduction: Introduction.
  418. * invoking Bison: Invocation.
  419. * language semantics: Semantics.
  420. * layout of Bison grammar: Grammar Layout.
  421. * left recursion: Recursion.
  422. * lexical analyzer: Lexical.
  423. * lexical analyzer, purpose: Bison Parser.
  424. * lexical analyzer, writing: Rpcalc Lexer.
  425. * lexical tie-in: Lexical Tie-ins.
  426. * literal token: Symbols.
  427. * look-ahead token: Look-Ahead.
  428. * main function in simple example: Rpcalc Main.
  429. * mid-rule actions: Mid-Rule Actions.
  430. * multi-function calculator: Multi-function Calc.
  431. * mutual recursion: Recursion.
  432. * nonterminal symbol: Symbols.
  433. * operator precedence: Precedence.
  434. * operator precedence, declaring: Precedence Decl.
  435. * options for Bison invocation: Invocation.
  436. * parse error: Error Reporting.
  437. * parser: Bison Parser.
  438. * parser stack: Algorithm.
  439. * parser state: Parser States.
  440. * polish notation calculator: RPN Calc.
  441. * precedence of operators: Precedence.
  442. * preventing warnings about conflicts: Expect Decl.
  443. * pure parser: Pure Decl.
  444. * recovery from errors: Error Recovery.
  445. * recursive rule: Recursion.
  446. * reduce/reduce conflict: Reduce/Reduce.
  447. * reduction: Algorithm.
  448. * reentrant parser: Pure Decl.
  449. * reverse polish notation: RPN Calc.
  450. * right recursion: Recursion.
  451. * rule syntax: Rules.
  452. * rules section for grammar: Grammar Rules.
  453. * running Bison (introduction): Rpcalc Gen.
  454. * semantic actions: Semantic Actions.
  455. * semantic value: Semantic Values.
  456. * semantic value type: Value Type.
  457. * semantics of the language: Semantics.
  458. * shift/reduce conflicts: Shift/Reduce.
  459. * shifting: Algorithm.
  460. * simple examples: Examples.
  461. * single-character literal: Symbols.
  462. * stack, parser: Algorithm.
  463. * stages in using Bison: Stages.
  464. * start symbol: Language and Grammar.
  465. * start-symbol, declaring: Start Decl.
  466. * state (of parser): Parser States.
  467. * summary, Bison declaration: Decl Summary.
  468. * summary, action features: Action Features.
  469. * symbol: Symbols.
  470. * symbol table example: Mfcalc Symtab.
  471. * symbols (abstract): Language and Grammar.
  472. * symbols in Bison, table of: Table of Symbols.
  473. * syntactic grouping: Language and Grammar.
  474. * syntax error: Error Reporting.
  475. * syntax of grammar rules: Rules.
  476. * terminal symbol: Symbols.
  477. * token: Language and Grammar.
  478. * token type: Symbols.
  479. * token type names, declaring: Token Decl.
  480. * tracing the parser: Debugging.
  481. * unary operator precedence: Contextual Precedence.
  482. * value type, semantic: Value Type.
  483. * value types, declaring: Union Decl.
  484. * value types, nonterminals, declaring: Type Decl.
  485. * warnings, preventing: Expect Decl.
  486. * writing a lexical analyzer: Rpcalc Lexer.
  487. * yychar: Look-Ahead.
  488. * yyclearin: Error Recovery.
  489. * yydebug: Debugging.
  490. * yyerrok: Error Recovery.
  491. * yyerror: Error Reporting.
  492. * yyerror: Rpcalc Error.
  493. * yylex: Lexical.
  494. * yylloc: Token Positions.
  495. * yylval: Token Values.
  496. * yynerrs: Error Reporting.
  497. * yyparse: Parser Function.
  498. * |: Rules.
  499.  
  500.  
  501.  
  502. Tag Table:
  503. Node: Top1138
  504. Node: Introduction2235
  505. Node: Conditions3309
  506. Node: Copying5162
  507. Node: Concepts18508
  508. Node: Language and Grammar19542
  509. Node: Grammar in Bison24008
  510. Node: Semantic Values25730
  511. Node: Semantic Actions27801
  512. Node: Bison Parser28978
  513. Node: Stages31213
  514. Node: Grammar Layout32430
  515. Node: Examples33672
  516. Node: RPN Calc34751
  517. Node: Rpcalc Decls35927
  518. Node: Rpcalc Rules37429
  519. Node: Rpcalc Input39159
  520. Node: Rpcalc Line40615
  521. Node: Rpcalc Expr41720
  522. Node: Rpcalc Lexer43671
  523. Node: Rpcalc Main46185
  524. Node: Rpcalc Error46561
  525. Node: Rpcalc Gen47534
  526. Node: Rpcalc Compile48642
  527. Node: Infix Calc49512
  528. Node: Simple Error Recovery52071
  529. Node: Multi-function Calc53946
  530. Node: Mfcalc Decl55484
  531. Node: Mfcalc Rules57436
  532. Node: Mfcalc Symtab58814
  533. Node: Exercises64961
  534. Node: Grammar File65469
  535. Node: Grammar Outline66237
  536. Node: C Declarations66994
  537. Node: Bison Declarations67595
  538. Node: Grammar Rules67987
  539. Node: C Code68419
  540. Node: Symbols69312
  541. Node: Rules72922
  542. Node: Recursion74544
  543. Node: Semantics76221
  544. Node: Value Type77310
  545. Node: Multiple Types77944
  546. Node: Actions78914
  547. Node: Action Types81277
  548. Node: Mid-Rule Actions82572
  549. Node: Declarations87849
  550. Node: Token Decl89092
  551. Node: Precedence Decl90396
  552. Node: Union Decl91943
  553. Node: Type Decl92780
  554. Node: Expect Decl93509
  555. Node: Start Decl95031
  556. Node: Pure Decl95428
  557. Node: Decl Summary96683
  558. Node: Multiple Parsers97884
  559. Node: Interface99569
  560. Node: Parser Function100404
  561. Node: Lexical101247
  562. Node: Calling Convention102631
  563. Node: Token Values103946
  564. Node: Token Positions105082
  565. Node: Pure Calling105956
  566. Node: Error Reporting106732
  567. Node: Action Features108436
  568. Node: Algorithm110921
  569. Node: Look-Ahead113041
  570. Node: Shift/Reduce115143
  571. Node: Precedence117531
  572. Node: Why Precedence118185
  573. Node: Using Precedence120037
  574. Node: Precedence Examples120998
  575. Node: How Precedence121697
  576. Node: Contextual Precedence122798
  577. Node: Parser States124586
  578. Node: Reduce/Reduce125820
  579. Node: Error Recovery128970
  580. Node: Context Dependency133818
  581. Node: Semantic Tokens134651
  582. Node: Lexical Tie-ins137674
  583. Node: Tie-in Recovery139167
  584. Node: Debugging141319
  585. Node: Invocation143736
  586. Node: Table of Symbols146257
  587. Node: Glossary151408
  588. Node: Index156729
  589.